【算法概论】动态规划：最短路径问题

因为刚开始想着，既然在图中表示，就要用到图的存储结构等等吧，所以 ?

首先，要复习一下图的相关知识（学完数据结构后过了不长的时间，已经还给老师了?）

1、图的存储结构：

       邻接矩阵表示法 和 邻接表表示法(详见 图 - 邻接表表示法)。

2、图的基本算法：

       计算图的顶点数量，计算图的边数量，返回第i个顶点的值，插入一个顶点，删除一个顶点，插入一条边，删除一条边，深度优先遍历图，广度优先遍历图。

       拓扑排序

接着，来看下面这道多段图中的最短路径问题（The shortest path in multistage graphs）：

问题描述：

       建立一个从源点S到终点T的多段图，设计一个动态规划算法求出从S到T的最短路径值，并输出相应的最短路径。 

解决思路（老师讲课）：

       首先，暴力法是遍历从 S 到 T 的所有路径，依次比较。

       但我们可以使用更优的方法 —— 动态规划。

       很容易看出，这是一个多阶段决策的问题，S —— A、B、C —— D、E、F —— T 分别是四个阶段，如下图所示：

       按照 自底向上(bottom-up) 的方法，d(S, T) = min{ 1 + d(A, T), 2 + d(B, T), 5 + d(C, T) }；这满足 动态规划 的 最优子结构 的性质，即，问题的最优解包含其子问题的最优解。

算法实现（老师讲课）：

有向无环图中的最短路径问题（The shortest path in dags）：

问题描述：

       建立一个从源点S到终点E的有向无环图，设计一个动态规划算法求出从S到E的最短路径值，并输出相应的最短路径。

解决思路（老师讲课）：

       有向无环图不像多段图，有明确的分阶段，它能转换成多段图进行求解吗？

       也可以，因为，有向无环图 可以通过 拓扑排序 将其转换为 线性结构。

       Notice that, the special distinguishing feature of a dag is that its nodes can be linearized; that is, they can be arranged on a line so that all edges go from left to right. 如下图所示：

        （回到了这篇文章开头的地方）。

算法实现：

       从图中可以看出：

       所以我本来想着要用着邻接表啊一些数据结构的知识，便复习了一番，最终代码太繁琐，在deadline之前调不完了……

……so，先暂空着……

However，

       在网上查找相关代码的时候，发现了如下的代码，自己又改了一部分：